#include<iostream>
#include<vector>
using namespace std;

//面试题17.16.按摩师
int massage(vector<int>& nums){
    int n = nums.size();
    if(n==0){
        return 0;
    }

    //状态表示 dp[i]表示以i为结尾，到达该位置时的最长预约时间
    //继续细分为两个状态表示
    //f[i]表示以i为结尾，到达该位置时，选择nums[i]，此时的最长预约时间
    //g[i]表示以i为结尾，到达该位置时，不选择nums[i]，此时的最长预约时间
    int f[n], g[n];

    //初始化
    f[0] = nums[0], g[0] = 0;

    //填表
    for (int i = 1; i < n; i++){
        //状态转移方程
        f[i] = g[i - 1] + nums[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }

    //返回值
    return max(f[n - 1], g[n - 1]);
}



//213.打家劫舍2
int rob1(vector<int>& nums,int begin,int end){
    if (begin > end){
        return 0;
    }
    //打家劫舍1思路

    int n = nums.size();
    //状态表示
    int f[n], g[n];

    //初始化
    f[begin] = nums[begin], g[begin] = 0;

    //填表
    for (int i = begin + 1; i <= end; i++){
        //状态转移方程
        f[i] = g[i - 1] + nums[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }

    return max(f[end], g[end]);
}
int rob(vector<int>& nums){
    int n = nums.size();

    //第一个位置有两种情况
    //如果第一个位置选，第二个位置和最后一个位置就不能选，从第三个位置到倒数第二个位置随便选
    //如果第一个位置不选，从第二个位置到最后一个位置随便选
    return max(rob1(nums, 2, n - 2) + nums[0], rob1(nums, 1, n - 1));
}




//740.删除并获得点数
int deleteAndEarn(vector<int>& nums){
    //找到元素中最大的值
    int maxnum = 0;
    for(auto x : nums){
        maxnum = max(x, maxnum);
    }
    //创建一个预处理数组,将原数组中相同值的和，以值为下标存放到预处理数组中
    vector<int> arr(maxnum + 1);
    for (int i = 0; i < nums.size(); i++){
        arr[nums[i]] += nums[i];
    }

    //转换成打家劫舍思路，相邻位置的值不选
    //状态表示
    int n = arr.size();
    int f[n], g[n];

    //初始化
    f[0] = arr[0], g[0] = 0;

    //填表
    for (int i = 1; i < n; i++){
        //状态表示
        f[i] = g[i - 1] + arr[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }

    //返回值
    return max(f[n - 1], g[n - 1]);
}




//LCR.091.粉刷房子
int minCost(vector<vector<int>>& costs){
    //先获取房子的个数
    int n = costs.size();

    //状态表示,dp[i]表示以下标i为结尾时，粉刷到当前下标房子的最小花费，而下标为i的房子有三种粉刷情况，继续细分
    //dp[i][0]表示以下标i为为结尾时，粉刷到当前下标房子为红色的最小花费,dp[i][1]表示蓝色,dp[i][2]表示绿色
    vector<vector<int>> dp(n + 1, vector<int>(3));

    //初始化 虚拟下标设置为0
    dp[0][0] = dp[0][1] = dp[0][2] = 0;

    //填表
    for (int i = 1; i <= n; i++){
        //三个状态转移方程
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
    }

    //返回值 取最后一个房子三种情况中最小的花费
    return min(min(dp[n][0], dp[n][1]), dp[n][2]);
}




//309.买卖股票的最佳时机含冷却期
int maxProfit(vector<int>& prices){
    int n = prices.size();

    //状态表示，dp[i]表示第i天结束时，此时的最大利润，第i天结束时有三种状态，继续细分
    //dp[i][0]表示第i天结束时，处于买入状态，此时的最大利润,dp[i][1]表示可交易状态，dp[i][2]表示冷却状态
    vector<vector<int>> dp(n + 1, vector<int>(3));

    //初始化
    //第0天结束时，处于买入状态，说明买下第0天的股票，此时的最大利润为负值
    dp[0][0] = 0 - prices[0];
    //第0天结束时，处于可交易状态，说明第0天啥也不干，此时的最大利润为0
    dp[0][1] = 0;
    //第0天结束时，处于冷却状态，说明第0天当天买，当天卖，此时的最大利润为0
    dp[0][2] = 0;

    //填表
    for (int i = 1; i < n; i++){
        //第i天结束时，处于买入状态，第i-1天可以处于买入状态或者处于可交易状态
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        //第i天结束时，处于可交易状态，第i-1天可以处于可交易状态或者处于冷却状态
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
        //第i天结束时，处于冷却状态，第i-1天只能处于买入状态
        dp[i][2] = dp[i - 1][0] + prices[i];
    }

    //返回值 最有一天处于买入状态时，利润一定不是最大，所以只能从其他两个状态中找到最大利润
    return max(dp[n - 1][1], dp[n - 1][2]);
}


//714.买股票的最佳时机含手续费
int maxProfit(vector<int>& prices, int fee){
    int n = prices.size();

    //状态表示，dp[i]表示第i天结束时，此时的最大利润，第i天结束时有两种状态，继续细分
    //dp[i][0]表示第i天结束时，处于买入状态，此时的最大利润；dp[i][1]表示卖出状态
    vector<vector<int>> dp(n, vector<int>(2));

    //初始化
    //第0天结束，处于买入状态，此时的最大利润为负值
    dp[0][0] = 0 - prices[0];
    //第0天结束时，处于卖出状态，说明第0天当天啥也不干
    dp[0][1] = 0;

    //填表
    for (int i = 1; i < n; i++){
        //第i天结束时，处于买入状态，第i-1天可以处于买入状态也可以处于卖出状态
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        //第i天结束时，处于卖出状态，第i-1天可以是买入状态也可以是卖出状态
        dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
    }

    //返回值 最后一天只能是卖出状态利润才能最大
    return dp[n-1][1];
}


//123.买卖股票的最佳时机3（最多交易两次）
const int INF = 0x3f3f3f3f;
int maxProfit(vector<int>& prices){
    int n = prices.size();

    //状态表示，dp[i]表示第i天结束时，此时的最大利润，第i天有多种状态，可能是买入，或者卖出，也可能交易一次或者交易两次，继续细分
    //f[i][j]表示第i天结束时，交易j次，处于买入状态，此时的最大利润
    //g[i][j]表示第i天结束时，交易j次，处于卖出状态，此时的最大利润
    //题意要求最多交易两次
    vector<vector<int>> f(n, vector<int>(3,-INF));
    vector<vector<int>> g(n, vector<int>(3,-INF));

    //初始化
    //f[0][0]表示第0天结束时，交易0次，处于买入状态，此时的最大利润为负值,不可能出现第0天交易0次以上的情况
    f[0][0] = 0 - prices[0];
    //g[0][0]表示第0天结束时，交易0次，处于卖出状态，相当于啥也不干，最大利润为0
    g[0][0] = 0;

    //填表
    for (int i = 1; i < n; i++){
        for (int j = 0; j <= 2; j++){
            //第i天结束时，处于买入状态，第i-1天可以是买入状态也可以是卖出状态,交易次数都不变
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
            //第i天结束时，处于卖出状态，第i-1天可以是卖出状态啥也不干，也可以是买入状态，今天卖出，交易次数加一
            g[i][j] = g[i - 1][j];
            if(j-1>=0){
                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
    }

    //返回值 最后一天一定是卖出状态时，利润才会最大，找出交易某次后，利润最大的情况
    int ret = 0;
    for (int j = 0; j <= 2; j++){
        ret = max(ret, g[n - 1][j]);
    }
    return ret;
}


//188.买卖股票的最佳时机4（最多交易k次）
int maxProfit(int k, vector<int>& prices){
    int n = prices.size();

    //状态表示
    vector<vector<int>> f(n, vector<int>(k + 1, -INF));
    vector<vector<int>> g(n, vector<int>(k + 1, -INF));

    //初始化
    f[0][0] = 0 - prices[0], g[0][0] = 0;

    //填表
    for (int i = 1; i < n; i++){
        for (int j = 0; j <= k; j++){
            //状态转移方程
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
            g[i][j] = g[i - 1][j];
            if (j - 1 >= 0){
                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
    }

    //返回值
    int ret = 0;
    for (int j = 0; j <= k; j++){
        ret = max(ret, g[n - 1][j]);
    }
    return ret;
}


int main(){

    return 0;
}